package com.yeung.swordoffer;


import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;

/**
 * 从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
 */
public class 把二叉树打印成多行 {
    public static void main(String[] args) {
        Print(new TreeNode(1));
    }

    static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if(pRoot==null) return result;
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(pRoot);
        queue.add(new TreeNode(-1));//-1的值表示本层结束
        ArrayList<Integer> temp = new ArrayList<>();
        while (!queue.isEmpty()) {
            TreeNode head = queue.remove();
            if (head.val != -1) {
                temp.add(head.val);//读取本层的, 且把其左右孩子加入到加入到下一层
                if (head.left != null) queue.add(head.left);
                if (head.right != null) queue.add(head.right);
            } else {
                //本次读取完毕, 标记下一层
                if (temp.size() > 0) {
                    result.add(temp);
                    temp=new ArrayList<>();
                }
                queue.add(new TreeNode(-1));
                //终止循环
                if (queue.size() == 1 && queue.peek().val == -1) break; //只有一个元素了, 且是-1,标志位, 则停止
            }

        }
        return result;
    }

}
